package top100.dynamic;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/18 11:19
 * @description: 给你一个非负整数数组 nums 和一个整数 target 。
 * <p>
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * <p>
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 * 示例 2：
 * <p>
 * 输入：nums = [1], target = 1
 * 输出：1
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 20
 * 0 <= nums[i] <= 1000
 * 0 <= sum(nums[i]) <= 1000
 * -1000 <= target <= 1000
 */
public class Solution494 {
    public int bag(int[] weight, int[] value, int w) {
        int[][] dp = new int[weight.length][w + 1];
        //使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

        if (value[0] <= w) {
            dp[0][value[0]] = 1;
        }
        dp[0][0] = 1;
        int numZero = 0;//为啥要算左边,如果i号物品都用不上呢
        for (int i = 0; i < weight.length; i++) {
            if(weight[i] == 0) numZero++;
            dp[i][0] = (int)Math.pow(2, numZero);
        }
        for (int i = 1; i < weight.length; i++) {
            for (int j = 0; j <= w; j++) {
                //1.i号物品不用
                dp[i][j] = dp[i - 1][j];
                //2.i号物品用
                if (j >= weight[i]) {
                    dp[i][j] += dp[i - 1][j - weight[i]];
                }
            }
        }
        return dp[weight.length - 1][w];
    }

    public int findTargetSumWays(int[] nums, int target) {
        //x + y = sum
        //x - y = target
        //x = (sum + target) / 2
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum < Math.abs(target) || (target + sum) % 2 != 0) {//为啥是绝对值
            return 0;
        }
        return bag(nums, nums, (sum + target) / 2);
    }

    public static void main(String[] args) {
        Solution494 s = new Solution494();
        System.out.println(s.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }
}
